import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-15 9:08
 */
public class KMP {
    public static void main(String[] args) {
        String s1 = "abcbacbcbaa";
//        String s2 = "cbcba";
        String s2 = "abcaababc";
        int[] next1 = getNext(s2);
        int[] next2 = getNext2(s2);
        System.out.println(Arrays.toString(next1));
        System.out.println(Arrays.toString(next2));
        System.out.println(find(s1, s2, next1));
        System.out.println(find(s1, s2, next2));

    }

    public static int find(String string, String substring, int[] next){
        int i = 0, j = 0, len1 = string.length(), len2 = substring.length();
        while (i<len1 && j<len2) {
            if (j==-1 || string.charAt(i)==substring.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j==len2) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static int[] getNext(String substring) {
        int[] next = new int[substring.length()];
        int j = 0;
        next[0] = -1;
        int k = -1;
        while (j<substring.length()-1){
            if (k==-1 || substring.charAt(j)==substring.charAt(k)) {

                if (substring.charAt(j+1)==substring.charAt(k+1)) {
                    next[++j] = next[++k];
                } else {
                    next[++j] = ++k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static int[] getNext2(String substring) {
        int[] next = new int[substring.length()+1];
        int j = 0;
        next[0] = -1;
        int k = -1;
        while (j < substring.length()){
            while (k!=-1 && substring.charAt(j)!=substring.charAt(k)){
                k = next[k];
            }

            j++;
            k++;
            next[j] = k;
        }
        return next;
    }
}



